НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №5
з навчальної дисципліни “Програмування складних алгоритмів”
Тема: «Лінійні однозв’язні та двозв’язні списки»
Варіант № 20
Дата «18» червня 2022
Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою.
Завдання до лабораторної роботи:
1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та наступні поміняти місцями. Виконати завдання згідно варіанту.
2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозв’язним списком.
Завдання для варіанту 20: Видалити зі стеку всі елементи, які знаходяться перед мінімальним.
Теоретичні відомості
Списками називається динамічна структура даних, що являє собою множину зі змінної кількості елементів, що представлені в одному і тому ж форматі. Вони мають механізми для додавання та видалення певних елементів. Довжина списку дорівнює кількості елементів, які містяться в списку, список з нульовою довжиною називається порожнім списком. Списки є одним з методів організації множини даних, в якому елементи певного типу утворюють ланцюжок.
Структура, в якій кожен елемент заданий в певному форматі та вони пов’язані між собою за допомогою вказівників, що записані в самих елементах, називається зв’язним списком.
Елементи списків прийнято задавати як структуру даних з двома або більше полями — полем даних та вказівником на сусідній елемент. Поле вказівника останнього елемента на наступний, так само як поле вказівника першого елемента на попередній, повинно містити пустий вказівник — NULL.
Сам список буде являти собою посилання на перший його елемент, який прийнято називати head. Також може мати посилання на останній елемент списка — tail.
Однозв’язний список – це структура даних, що представляє з себе множину елементів, кожен з яких містить посилання на наступний елемент. Посилання в останньому елементі вказує на NULL.
/
Рисунок 1 — Візуалізація роботи однозв’язного списку
Елементарними функціями над однозв’язними списками є:
ініціалізація списку;
додавання елемента у список;
видалення елемента зі списку;
друк (виведення) списку;
пошук даних у списку.
Для оптимізації та прискорення деяких операцій у списках може бути доцільно мати можливість переходити між вершинами в обидва напрямки. Для цього застосовується така динамічна структура даних як двоспрямований (двозв'язний) список.
Двозв'язний список — це структура даних, що являє собою множину елементів, кожен з яких містить посилання на попередній та на наступний елемент. Посилання першого елемента на попередній та посилання останнього на наступний дорівнюють NULL.
Сам список можна представити як посилання на перший елемент списку, а також останній, що дозволить здійснювати обхід списку з кінця в оберненому напрямку.
/
Рисунок 2 — Візуалізація роботи двозв’язного списку
Стек — це динамічна структура даних, що зазвичай побудована на основі лінійного списку та працює за принципом LIFO (last in, first out, з англ. останнім прийшов – першим вийшов). Це означає, що елемент, що був останнім доданий в стек, буде витягнутий з нього в першу чергу.
На відміну від списків, в стеку не можна отримати доступ до довільного елемента. Є можливість лише видаляти або додавати елементи, використовуючи особливі методи.
Для пояснення стеку часто використовують аналогії з реального життя. Прикладом може послугувати стопка тарілок. Кожна нова тарілка ставиться зверху, а коли ми беремо тарілку зі стопки, то беремо її зверху, тобто ту, яку поставили останньою.
Отже, стек має такі властивості:
додаванняя елементів завжди відбувається з одного і того ж боку;
діставання елементів завжди відбувається з того ж боку, що і додавання;
доступ можна отрима...
